#include <iostream>
#include <vector>
using namespace std;
void Merge(vector<int>& a, int left, int right, int mid) {
    vector<int> temp;
    int l = left, r = mid + 1;
    while(l <= mid && r <= right) {
        if(a[l] < a[r]) {
            temp.push_back(a[l++]);
        }else {
            temp.push_back(a[r++]);
        }
    }
    while(l <= mid) temp.push_back(a[l++]);
    while(r <= right) temp.push_back(a[r++]);
    for(int i = 0; i < temp.size(); i++) {
        a[left + i] = temp[i];
    }
}
void MergeSort(vector<int>& a, int left, int right) {
    if(left >= right) return;
    int mid = left + (right - left) / 2;
    MergeSort(a, left, mid);
    MergeSort(a, mid + 1, right);
    Merge(a, left, right, mid);
}
void MergeNR(vector<int>& a, int left, int mid, int right, vector<int>& temp) {
    int l = left, r = mid + 1;
    int i = left;
    while(l <= mid && r <= right) {
        if(a[l] < a[r]) {
            temp[i++] = a[l++];
        }else {
            temp[i++] = a[r++];
        }
    }
    while(l <= mid) temp[i++] = a[l++];
    while(r <= right) temp[i++] = a[r++];
    for(int k = left; k <= right; k++) {
        a[k] = temp[k];
    }

}
// 归并排序非递归实现
void MergeSortNonR(vector<int>& a, int n) {
    vector<int> temp(n);
    for(int gap = 1; gap < n; gap *= 2) {
        for(int i = 0; i < n - gap; i += 2*gap) {
            int left = i;
            int mid = i + gap - 1;
            int right = min(i + 2*gap - 1, n - 1);
            MergeNR(a, left, mid, right, temp);
        }
    }
}
int main() {
    vector<int> a =  {1, 4, 3, 5, 6, 3, 2, 7, 8, 0};
    // MergeSort(a, 0, 9);
    MergeSortNonR(a, 10);
    for(auto& e : a) {
        cout << e << " ";
    }
    return 0;
}